package com.zyk.grate_offer.class06;

/**
 * @author zhangsan
 * @date 2021/5/10 20:35
 */
public class Code02_MaximumXorOfTowNumbersInAnArray {

    // 暴力解 O(N^2)
    public static int findMaximumXOR(int[] nums) {
        int N = nums.length, max = 0;
        for (int i = 0; i < N - 1; i++) {
            int pre = nums[i];
            for (int j = i + 1; j < N; j++) {
                max = Math.max(max, pre ^ nums[j]);
            }
        }
        return max;
    }


    // 找出哪儿两个数异或的结果最大. 返回
    // O(N)解: 把所有数都加入到前缀树上. nums[i], 遍历maxXor一遍.
    // ?? 会异或到自己, 但题目说明都是正数所以自己异或自己是0,肯定不是最大的
    public static int findMaximumXOR2(int[] nums) {
        int max = 0;
        NumTrie tree = new NumTrie();
        for (int num : nums) {
            tree.addNumber(num);
        }
        for (int num : nums) {
            max = Math.max(max, tree.maxXor(num));
        }
        return max;
    }

    public static class NumTrie {

        Node head = new Node();

        public void addNumber(int num) {
            int path;
            Node cur = head;
            for (int i = 30; i >= 0; i--) {     // 题目都是正数, 这里不考虑最高位
                path = (num >> i) & 1;
                if (cur.nexts[path] == null)
                    cur.nexts[path] = new Node();
                cur = cur.nexts[path];
            }
        }

        // 之前已经收集一堆数字, 你给我一个数我给你返回和收集一堆数最大的异或结果
        public int maxXor(int num) {
            int path, best, res = 0;        // path: num第i位实际的值.   best: 想要得到最大结果和谁走哪儿条路最好
            Node cur = head;
            for (int i = 30; i >= 0; i--) {
                path = (num >> i) & 1;
                best = (path ^ 1);
                best = cur.nexts[best] == null ? path : best;
                res |= (path ^ best) << i;
                cur = cur.nexts[best];
            }
            return res;
        }

        public static class Node {
            Node[] nexts = new Node[2];
        }
    }

}
